// 124.二叉树的最大路径和
package LeetcodeHot100;


public class Solution124 {
    public int max = Integer.MIN_VALUE; // 全局最大值

    public int maxPathSum(TreeNode root) {
        DFS(root);
        return max; // 返回全局最大值
    }

    // DFS 返回当前结点的最大路径和，局部最大值
    public int DFS(TreeNode root) {
        int currentValue = root.val;
        int left = 0;
        int right = 0;
        if (root.left != null) {
            left = DFS(root.left);
            currentValue += left > 0 ? left : 0;
        }
        if (root.right != null) {
            right = DFS(root.right);
            currentValue += right > 0 ? right : 0;
        }
        // 当前结点的最大路径和等于 val + 左右子树(如果值大于0)
        max = Math.max(max, currentValue);
        // 返回给父节点的值为 val + 左子树或右子树或空
        return root.val + (Math.max(left, right) > 0 ? Math.max(left, right) : 0);
    }
}